import pprint

"""
做了2个小时，超时了。。。
"""


class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)

        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1

        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = 1

        for i in range(3, n + 1):
            for j in range(n - i + 1):
                if s[j] == s[j + i - 1] and dp[j + 1][j + i - 2]:
                    dp[j][j + i - 1] = 1
        # pprint.pprint(dp)
        res = float("inf")

        def find(start, length):
            nonlocal res
            if start == n:
                res = min(res, length)
            # print(start, length)
            for i in range(start, n):
                if dp[start][i] == 1:
                    # print("[", start, i, length, "]")
                    find(i + 1, length + 1)

        find(0, 0)
        return res - 1


if __name__ == "__main__":
    print(Solution().minCut("ababababababababababababcbabababababababababababa"))
